/*
 * ============================================================================
 * 栈 (Stack) - C++ 实现（模板版）
 * ============================================================================
 * LIFO 结构：push / pop / top 均为 O(1)。
 */

#include <iostream>
#include <vector>
#include <stdexcept>
#include <string>

// 数组实现的栈
template <typename T>
class ArrayStack {
public:
    void push(const T& v) { _data.push_back(v); }
    void pop() { if (empty()) throw std::runtime_error("empty"); _data.pop_back(); }
    T& top() { if (empty()) throw std::runtime_error("empty"); return _data.back(); }
    const T& top() const { if (empty()) throw std::runtime_error("empty"); return _data.back(); }
    bool empty() const { return _data.empty(); }
    size_t size() const { return _data.size(); }
    void print() const { std::cout << "栈底 → ["; for(size_t i=0;i<_data.size();++i){ std::cout<<_data[i]; if(i+1<_data.size()) std::cout<<", "; } std::cout << "] ← 栈顶\n"; }
private:
    std::vector<T> _data;
};

// 链表实现的栈
template <typename T>
struct SNode { T data; SNode* next; explicit SNode(const T& v):data(v),next(nullptr){} };

template <typename T>
class LinkedStack {
public:
    LinkedStack():_top(nullptr),_count(0){}
    ~LinkedStack(){ while(_top){ auto*t=_top; _top=_top->next; delete t; } }
    void push(const T& v){ auto*n=new SNode<T>(v); n->next=_top; _top=n; ++_count; }
    void pop(){ if(!_top) throw std::runtime_error("empty"); auto*t=_top; _top=_top->next; delete t; --_count; }
    T& top(){ if(!_top) throw std::runtime_error("empty"); return _top->data; }
    bool empty() const { return _top==nullptr; }
    size_t size() const { return _count; }
private:
    SNode<T>* _top; size_t _count;
};

// 应用场景1：括号匹配
bool isPair(char a, char b){ return (a=='('&&b==')')||(a=='['&&b==']')||(a=='{'&&b=='}'); }
bool isBalanced(const std::string& s){ ArrayStack<char> st; for(char c: s){ if(c=='('||c=='['||c=='{') st.push(c); else if(c==')'||c==']'||c=='}'){ if(st.empty()||!isPair(st.top(),c)) return false; st.pop(); } } return st.empty(); }

// 应用场景2：后缀表达式求值
int evalPostfix(const std::string& expr){ ArrayStack<int> st; for(size_t i=0;i<expr.size();++i){ char c=expr[i]; if(c==' ') continue; if(std::isdigit((unsigned char)c)){ st.push(c-'0'); } else { int b=st.top(); st.pop(); int a=st.top(); st.pop(); int r=0; switch(c){ case '+': r=a+b; break; case '-': r=a-b; break; case '*': r=a*b; break; case '/': r=a/b; break; } st.push(r);} } return st.top(); }

int main(){
    std::cout << "╔════════════════════════════════════════╗\n";
    std::cout << "║   栈 (Stack) - C++ 实现                ║\n";
    std::cout << "╚════════════════════════════════════════╝\n";

    std::cout << "\n--- 数组栈 ---\n";
    ArrayStack<int> s; s.push(10); s.push(20); s.push(30); s.print();
    std::cout << "弹出: " << s.top() << "\n"; s.pop(); s.print();

    std::cout << "\n--- 链表栈 ---\n";
    LinkedStack<int> ls; ls.push(100); ls.push(200); ls.push(300); std::cout << "栈顶:" << ls.top() << ", 大小:" << ls.size() << "\n"; ls.pop(); std::cout << "弹出后大小:" << ls.size() << "\n";

    std::cout << "\n--- 括号匹配 ---\n";
    std::string t1 = "{[()]}"; std::string t2 = "{[(])}";
    std::cout << "  " << t1 << " → " << (isBalanced(t1)?"匹配✓":"不匹配✗") << "\n";
    std::cout << "  " << t2 << " → " << (isBalanced(t2)?"匹配✓":"不匹配✗") << "\n";

    std::cout << "\n--- 后缀表达式 ---\n";
    std::string postfix = "5 3 + 2 *"; // 16
    std::cout << "  " << postfix << " = " << evalPostfix(postfix) << "\n";

    std::cout << "\n✅ 优势: O(1)操作, LIFO适配诸多场景\n";
    std::cout << "⚠️ 局限: 只能访问栈顶\n";
    return 0;
}
